package primary.primary0;

import java.util.*;

/**
 *
 */
public class S0133克隆图 {
    /**
     * 注意这里一个int就对应唯一一个node
     */
    public Node cloneGraph(Node node) {
        // 先遍历本来的node, 把它的关系存在一个map里面
        Map<Integer, List<Integer>> graph = new HashMap<>();
        // todo: 遍历本来node, 一边遍历一遍复制, 新旧node用map来连接比较合适
        Deque<Node> iterDeque = new LinkedList<>();
        Set<Node> visitedSet = new HashSet<>();
        iterDeque.addLast(node);
        visitedSet.add(node);
        while(!iterDeque.isEmpty()){
            Node curNode = iterDeque.pollFirst();
            Node curNodeCopy = new Node(curNode.val);

            List<Node> neighbors = curNode.neighbors;
            if(!graph.containsKey(curNode.val))
                graph.put(curNode.val, new LinkedList<>());
            List<Integer> curNodeAimList = graph.get(curNode.val);
            for(Node tempNode: neighbors){
                curNodeAimList.add(tempNode.val);
                visitedSet.add(tempNode);
                if(!visitedSet.contains(tempNode))
                    iterDeque.addLast(tempNode);
            }
        }

        // 使用graph来复制一个图


        return null;
    }
}
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
